Palindrome partitioning

Time: O(N2)~O(2N); Space: O(N^2); medium

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example 1:

Input: “aab”

Output:

[
  ["aa","b"],
  ["a","a","b"]
]

Explanation:

  • There are 2 ways to split “aab”.

    1. Split “aab” into “aa” and “b”, both palindrome.

    2. Split “aab” into “a”, “a”, and “b”, all palindrome.

[6]:

class Solution1(object):
    """
    Time: O(N^2~2^N)
    Space: O(N^2)
    """
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        n = len(s)

        is_palindrome = [[0 for j in range(n)] for i in range(n)]
        for i in reversed(range(0, n)):
            for j in range(i, n):
                is_palindrome[i][j] = s[i] == s[j] and ((j - i < 2 ) or is_palindrome[i + 1][j - 1])

        sub_partition = [[] for i in range(n)]
        for i in reversed(range(n)):
            for j in range(i, n):
                if is_palindrome[i][j]:
                    if j + 1 < n:
                        for p in sub_partition[j + 1]:
                            sub_partition[i].append([s[i:j + 1]] + p)
                    else:
                        sub_partition[i].append([s[i:j + 1]])

        return sub_partition[0]

[11]:

s = Solution1()
s = "aab"
# print(s.partition(s))     # ('', 'aab', '')
# assert s.partition(s) == [
#   ["a","a","b"],
#   ["aa","b"]
# ]

2. Recursive solution

[13]:

class Solution2(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        result = []
        self.partitionRecu(result, [], s, 0)
        return result

    def partitionRecu(self, result, cur, s, i):
        if i == len(s):
            result.append(list(cur))
        else:
            for j in range(i, len(s)):
                if self.isPalindrome(s[i: j + 1]):
                    cur.append(s[i: j + 1])
                    self.partitionRecu(result, cur, s, j + 1)
                    cur.pop()

    def isPalindrome(self, s):
        for i in range(len(s) // 2):
            if s[i] != s[-(i + 1)]:
                return False
        return True

[14]:

s = Solution2()
s = "aab"
# print(s.partition(s))     # ('', 'aab', '')
# assert s.partition(s) == [
#   ["aa","b"],
#   ["a","a","b"]
# ]

('', 'aab', '')

[15]:

class Solution3(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if not s:
            return [[]]
        result = []
        for i in range(len(s)):
            if self.isPalindrome(s[:i + 1]):
                for r in self.partition(s[i + 1:]):
                    result.append([s[:i + 1]] + r)
        return result

    def isPalindrome(self, s):
        return s == s[::-1]

[17]:

s = Solution3()
s = "aab"
# print(s.partition(s))     # ('', 'aab', '')
# assert s.partition(s) == [
#   ["aa","b"],
#   ["a","a","b"]
# ]